package org.leetcode.middle.leetcode236;

import org.leetcode.TreeNode;

public class Solution {


    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null){
            return root;
        }

        if (root==p || root==q){
            return root;
        }

        TreeNode left = lowestCommonAncestor3(root.left,p,q);
        TreeNode right = lowestCommonAncestor3(root.right,p,q);

        if (left!=null && right!=null){
            return root;
        }else if (left==null && right!=null){
            return right;
        }else if (left!=null && right==null){
            return left;
        }else {
            return null;
        }

    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        //当前节点是目标节点之一
        if (root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor2(root.left, p, q);
        TreeNode right = lowestCommonAncestor2(root.right, p, q);

        //当前节点的左子树和右子树中都包含目标节点
        if (left != null && right != null) {
            return root;
        }

        //当前的节点的左子树和右子树中有一个或者都没有包含目标节点
        return left != null ? left : right;

    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null) {
            return null;
        }

        if (root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right == null) {
            return left;
        } else if (left == null && right != null) {
            return right;
        } else if (left != null && right != null) {
            return root;
        } else {
            return null;
        }

    }
}
